package graph.unweighted.bfs.demo;

import java.util.ArrayList;
import java.util.Collections;

import queue.CandyLoopQueue;

/**
 * 
 * @Title: WaterPazzle.java 
 * @Package graph.bfs.demo 
 * @Description: 问题描述：有两个水桶，一个可以装5升水，一个可以装3升水。怎么利用两个水桶得到4升水？
 *               思路：可以使用图的广度优先搜索的算法进行最短步骤的求解。
 * @author CandyWall   
 * @date 2021年1月18日 上午11:07:23 
 * @version V1.0
 */
public class WaterPuzzle {
    private boolean[] visited;
    private int[] pres;
    
    public int solve() {
        visited = new boolean[54];
        
        pres = new int[54];
        for(int i = 0; i < 54; i++) {
            pres[i] = -1;
        }
        
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(0);
        visited[0] = true;
        while(!queue.isEmpty()) {
            Integer v = queue.dequeue();
            visited[v] = true;
            ArrayList<Integer> nexts = new ArrayList<>();
            // 当前两个水桶a、b中分别有x升和y升水
            int x = v / 10, y = v % 10;
            // 1、将a中的水倒掉
            nexts.add(y);
            // 2、将b中的水倒掉
            nexts.add(x * 10);
            // 3、将a装满
            nexts.add(5 * 10 + y);
            // 4、将b装满
            nexts.add(x * 10 + 3);
            // 5、将a中的水倒入b中
            // b中剩余容量
            int bLeft = 3 - y;
            // a中可以倒出的水必须为a的容量和b中的剩余容量的两者的最小值
            int aPour = Math.min(x, bLeft);
            nexts.add((x - aPour) * 10 + y + aPour);
            // 6、将b中的水倒入a中
            int aLeft = 5 - x;
            int bPour = Math.min(y, aLeft);
            nexts.add((x + bPour) * 10 + y - bPour);
            
            for(int w : nexts) {
                if(!visited[w]) {
                    queue.enqueue(w);
                    pres[w] = v;
                    // 如果a桶中有4升水，目标达成
                    if(w / 10 == 4) {
                        return w;
                    }
                }
            }
        }
        return -1;
    }
    
    /**
     * 获取两个倒水获取4升水的步骤
     * @return
     */
    public ArrayList<Integer> getWaterPourSteps() {
        ArrayList<Integer> steps = new ArrayList<>();
        int cur = solve();
        if(cur == -1) {
            return steps;
        }
        while(cur != 0) {
            steps.add(cur);
            cur = pres[cur];
        }
        steps.add(0);
        Collections.reverse(steps);
        return steps;
    }
    
    public static void main(String[] args) {
        System.out.println(new WaterPuzzle().getWaterPourSteps());
    }
}
